package wwl.lsf;

/**
 * @Title
 * @Author wangwenliang
 * @Date 2021/3/30
 * @Description
 */
public class 寻找两个正序数组的中位数 {
    public static void main(String[] args) {

        int[] a = {1, 3, 4, 34};
        int[] b = {2, 4, 5, 6, 345, 5555};
        寻找两个正序数组的中位数 sz = new 寻找两个正序数组的中位数();
        System.out.println("sz.findMedianSortedArrays(a, b) = " + sz.findMedianSortedArrays3(a, b));
        System.out.println("sz.findZ(a, b) = " + sz.findZ3(a, b));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums;
        int m = nums1.length;
        int n = nums2.length;
        nums = new int[m + n];
        if (m == 0) {
            if (n % 2 == 0) {
                return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
            } else {

                return nums2[n / 2];
            }
        }
        if (n == 0) {
            if (m % 2 == 0) {
                return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
            } else {
                return nums1[m / 2];
            }
        }

        int count = 0;
        int i = 0, j = 0;
        while (count != (m + n)) {
            if (i == m) {
                while (j != n) {
                    nums[count++] = nums2[j++];
                }
                break;
            }
            if (j == n) {
                while (i != m) {
                    nums[count++] = nums1[i++];
                }
                break;
            }

            if (nums1[i] < nums2[j]) {
                nums[count++] = nums1[i++];
            } else {
                nums[count++] = nums2[j++];
            }
        }

        if (count % 2 == 0) {
            return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
        } else {
            return nums[count / 2];
        }
    }

    public double findZ(int[] nums1, int[] nums2) {
        int[] all;
        int size1 = nums1.length;
        int size2 = nums2.length;
        all = new int[size1 + size2];

        if (size1 == 0) {
            return getMiddle(nums2);
        }
        if (size2 == 0) {
            return getMiddle(nums1);
        }

        int i = 0, j = 0, count = 0;

        while (count != all.length) {
            if (i == size1) {
                while (j != size2) {
                    all[count++] = nums2[j++];
                }
                break;
            }
            if (j == size2) {
                while (i != size1) {
                    all[count++] = nums1[i++];
                }
                break;
            }
            if (nums1[i] < nums2[j]) {
                all[count++] = nums1[i++];
            } else {
                all[count++] = nums2[j++];
            }
        }

        return getMiddle(all);
    }

    public double findZ2(int[] nums1, int[] nums2) {
        int size1 = nums1.length;
        int size2 = nums2.length;
        int left = -1, right = -1, aStart = 0, bStart = 0;
        int allSize = size1 + size2;

        for (int i = 0; i <= allSize / 2; i++) {

            left = right;
            if (aStart < size1 && (bStart >= size2 || nums1[aStart] < nums2[bStart])) {
                right = nums1[aStart++];
            } else {
                right = nums2[bStart++];
            }
        }

        if ((allSize & 1) == 1) {
            return right;
        } else {
            return (left + right) / 2.0;
        }
    }

    public double findZ3(int[] nums1, int[] nums2) {
        int aSize = nums1.length;
        int bSize = nums2.length;
        int left = (aSize + bSize + 1) / 2;
        int right = (aSize + bSize + 2) / 2;

        return (getKthMy(nums1, 0, aSize - 1, nums2, 0, bSize - 1, left) +
                getKthMy(nums1, 0, aSize - 1, nums2, 0, bSize - 1, right)) / 2.0;

    }

    /**
     * @param nums1
     * @param begin1
     * @param end1
     * @param nums2
     * @param begin2
     * @param end2
     * @param k      第k小 比索引大1
     * @return
     */
    private int getKthMy(int[] nums1, int begin1, int end1, int[] nums2, int begin2, int end2, int k) {

        int length1 = end1 - begin1 + 1;
        int length2 = end2 - begin2 + 1;

        if (length1 > length2) {
            getKthMy(nums2, begin2, end2, nums1, begin1, end1, k);
        }

        if (length1 == 0) {
            //因为要取索引所以要-1
            return nums2[begin2 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[begin1], nums2[begin2]);
        }

        int i = begin1 + Math.min(length1, k / 2) - 1;
        int j = begin2 + Math.min(length2, k / 2) - 1;
        if (nums1[i] > nums2[j]) {
            //可以防止直接超过长度了,那就用长度的
            k = k - (j - begin2 + 1);
            begin2 = j + 1;
        } else {
            k = k - (i - begin1 + 1);
            begin1 = i + 1;
        }
        return getKthMy(nums1, begin1, end1, nums2, begin2, end2, k);
    }

    public double getMiddle(int[] all) {
        if ((all.length & 1) == 0) {
            return (all[all.length / 2 - 1] + all[all.length / 2]) / 2.0;
        } else {
            return all[all.length / 2];
        }

    }

    public double findMedianSortedArrays2(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int len = m + n;
        int left = -1, right = -1;
        int aStart = 0, bStart = 0;
        for (int i = 0; i <= len / 2; i++) {
            left = right;
            if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
                right = A[aStart++];
            } else {
                right = B[bStart++];
            }
        }
        if ((len & 1) == 0)
            return (left + right) / 2.0;
        else
            return right;
    }


    public double findMedianSortedArrays3(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }

    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if (len1 > len2) {
            return getKth(nums2, start2, end2, nums1, start1, end1, k);
        }
        if (len1 == 0) {
            return nums2[start2 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        } else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

    public double findMedianSortedArrays4(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) {
            // 保证 m <= n
            return findMedianSortedArrays(B, A);
        }

        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j != 0 && i != m && B[j - 1] > A[i]) { // i 需要增大
                iMin = i + 1;
            } else if (i != 0 && j != n && A[i - 1] > B[j]) { // i 需要减小
                iMax = i - 1;
            } else { // 达到要求，并且将边界条件列出来单独考虑
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[j - 1];
                } else if (j == 0) {
                    maxLeft = A[i - 1];
                } else {
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                } // 奇数的话不需要考虑右半部分

                int minRight = 0;
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(B[j], A[i]);
                }

                return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
            }
        }
        return 0.0;
    }


}
